package main

import "fmt"
import "strings"
import "flag"

import "os"
import "bufio"

import "eh/grammar"

// Section Two: States and Statesets ------------------------------

type StateSet struct
    {
    elements []*State
    }

func (ss *StateSet) parseResult( g *grammar.Type, b Builder ) [] Node {
    result := make([]Node, 0, ss.Size()) 
    count := 0
    for index := 0; index < ss.Size(); index += 1 {
        s := ss.elements[index]
        if s.IsCompleted() && s.rule.Name == grammar.Word("$ROOT") {
            fmt.Printf( ";;; completed: %v\n", s )
            result = result[0:count+1]
            result[count] = s.args[0]
            count += 1
        }
    }
    return result
}
   
func (ss *StateSet) addState( g *grammar.Type, b Builder, s *State ) {
    n := len(ss.elements)
    for _, x := range ss.elements { if s.EqState( x ) { return } }
    if n == cap(ss.elements) {
        bigger := make([]*State, (n + 1) * 2)
        copy( bigger, ss.elements )
        ss.elements = bigger
    }
    ss.elements = ss.elements[0:n+1]
    ss.elements[n] = s
}

func (ss *StateSet) IsEmpty() bool { return len(ss.elements) == 0 }
    
func (ss *StateSet) GetState( i int ) *State { return ss.elements[i] }

func NewStateSet() *StateSet { return &StateSet{make([]*State, 0)} }

func (ss *StateSet) Size() int { return len(ss.elements) }

func (parent *State) Wants( consider *State ) bool {
    return parent.rest.StartsWith( consider.rule.Name )
}

func (ss *StateSet) CompleteWith( g *grammar.Type, b Builder, consider *State ) {
    tree := b.makeNode( g, string(consider.rule.Tag), consider.args )
    for index := 0; index < consider.parents.Size(); index += 1 {
        parent := consider.parents.elements[index]
        if parent.Wants(consider) {
            ss.addState( g, b, parent.Advance( b, tree ) )
        }
    }
}

type State struct
    {
    rule *grammar.Rule
    rest *grammar.ItemList
    parents *StateSet
    args NodeSeq
    }
    
func (s *State) String() string {   
    body := ""
    items := s.rule.Rhs
    for items != nil {
        if items == s.rest { body += " |" }
        body = body + " " + string(items.This.Name)
        items = items.Rest
    }
    return "<" + string(s.rule.Name) + " :=" + body + ">"
}

func (s *State) EqState( other *State ) bool {
    return s.rule == other.rule && s.rest == other.rest && s.parents == other.parents && s.args.eq( other.args ) 
}
    
func (s *State) Advance( b Builder, t Node ) *State {
    return &State{s.rule, s.rest.Rest, s.parents, s.args.append(t)}
}
   
func NewState( p *grammar.Rule, rest *grammar.ItemList, s *StateSet, arg NodeSeq ) *State {
    result := &State{p, rest, s, arg}
    fmt.Printf( ";;; made new state, viz, %v\n", result )
    return result
}

func (s *State) Consumes( w grammar.Word ) bool {
    fmt.Printf( "(%v).Consumes(%v)? %v\n", s, w, s.rest.FirstWord() == w )
    return s.rest.FirstWord() == w
}

func (s *State) IsCompleted() bool {
    return s.rest == nil
}

// The Rest -------------------------------------------------------

type NodeSeq []Node

func (this NodeSeq) eq( that NodeSeq ) bool {
	n := len(this)
	if n != len(that) { return false }
	for i := 0; i < n; i += 1 {
		if !this[i].eq(that[i]) { return false }
	}
	return true
}

func (this NodeSeq) append( n Node ) NodeSeq {
	size := len(this)
    result := make([]Node, size + 1 )
    copy( result, this )
    result[size] = n
    return result
}

type Node interface
    {
    eq(Node) bool
    }
    
type Leaf interface 
    {
    Node
    }

    
type Builder interface
    {
    makeNode( *grammar.Type, string, NodeSeq ) Node
    makeLeaf( *grammar.Type, grammar.Word, string ) Leaf
    makeNil() NodeSeq 
    }

type Parser struct 
    {
    b Builder
    g *grammar.Type
    }


type Tokens struct 
    {
    them []string
    }
    
func (t *Tokens) next( g *grammar.Type ) grammar.Word {
    if len(t.them) == 0 { return "" }
    result := t.them[0]
    t.them = t.them[1:]
    return grammar.Word(result)
}

func tokensFrom( s string ) *Tokens {
    them := strings.Split( s, " ", 0 )
    return &Tokens{ them }
}


type MyBuilder struct {}

type MyNode struct {
    tag string
    spelling string
    args NodeSeq
}

func (m *MyNode) String() string {
    result := "(" + m.tag
    if m.spelling != "" {
        result = result + ":`" + m.spelling + "`"
    }
    for _, arg := range m.args {
        result = result + fmt.Sprintf( " %v", arg )
    }
    return result + ")"
}

func (m *MyNode) eq( other Node ) bool {
    return true
}

func (b *MyBuilder) makeNil() NodeSeq {
    return []Node{}
}

func (b *MyBuilder) makeLeaf( g *grammar.Type, w grammar.Word, s string ) Leaf {
    return &MyNode{string(w), s, make([]Node, 0)} 
}

func (b *MyBuilder) makeNode( g *grammar.Type, tag string, args NodeSeq ) Node {
    if tag == "$" { return args[0] }
    return &MyNode{tag, "", args}
}

var grammarString =
`
A ::= B B
B ::= X Y Z
`

var tokenString =
`X:x Y Z X:xx Y Z`

var gf *string = flag.String( "gf", "", "name of grammar file" )
var ts *string = flag.String( "ts", "", "token string" )

func stringFromFile( fileName string ) string {
    file, _ := os.Open( fileName, os.O_RDONLY, 0 )
    r := bufio.NewReader( file )
    s, _ := r.ReadString( 0 )
    return s
}

func loadGrammar() *grammar.Type {
    if *gf == "" { return grammar.GrammarFromString( grammarString ) }
    return grammar.GrammarFromString( stringFromFile( *gf ) )
}

func loadTokens() *Tokens {
    if *ts == "" { return tokensFrom( tokenString ) }
    return tokensFrom( *ts )
}

func main() {
    flag.Parse()
    builder := &MyBuilder{}
    grammar := loadGrammar() 
    p := Parser{builder, grammar}
    t := loadTokens() 
    them := rawParse( p, t )
    fmt.Printf( ">> result = %v\n", them )
}

func split( w grammar.Word ) (kind grammar.Word, spelling string) {
    slice := strings.Split( string(w), ":", 2 )
    if len(slice) < 2 { return w, string(w) }
    return grammar.Word(slice[0]), slice[1]
}

func rawParse( p Parser, tokens *Tokens ) [] Node {
    fmt.Printf( ";;; -- starting parse --------------------------\n" )
    build := p.b
    g := p.g
    rootProd := g.Root
    states := NewStateSet()
    rootRest := rootProd.Rhs
    initial := NewState( rootProd, rootRest, NewStateSet(), build.makeNil() )
    states.addState( g, build, initial )
    for {
        kind, spelling := split( tokens.next( g ) )
        fmt.Printf( ";;; ---- next iteration, stateset now %v ----\n", states )
        fmt.Printf( ";;; `%v`:%v.IsNull() = %v\n", spelling, kind.IsNull() )
        tree := build.makeLeaf( g, kind, spelling )
        seeds := NewStateSet()
        for index := 0; index < states.Size(); index += 1 {
            consider := states.GetState(index)
            fmt.Printf( ";;; considering state %v of %v, %v\n", index, len(states.elements), consider )
            if consider.IsCompleted() {
                fmt.Printf( ";;; consider is completed\n" )
                states.CompleteWith( g, build, consider )
            } else if consider.Consumes( kind ) {
                fmt.Printf( ";;; consider consumes %v\n", kind )
                seeds.addState( g, build, consider.Advance( build, tree ) );
            } else {
                first := consider.rest.FirstWord()
                fmt.Printf( ";;; have to try predicting for %v\n", first )
                for _, r := range g.RulesThatDefine( first ) {
                    if false { fmt.Printf( ";;; -- -- yay! %v\n", r ) }
                    s := NewState( r, r.Rhs, states, build.makeNil() )
                    states.addState( g, build, s )
                }
            }
        }
        if kind == "" { break }
        if seeds.IsEmpty() { return nil }
        fmt.Printf( ";;; seeds = %v\n", seeds )
        states = seeds
    }
    fmt.Printf( ";;; OK, the states we're left with are %v\n", states )
    return states.parseResult( g, build )
}

/*
Here is a sketch of an implementation-friendly variant of Tarjan's
algorithm computing what we need in case of FIRST (the three
set-computing statements added are marked by (*...!*) ).

        (* asssume that nonterminals are INTEGERs 0, 1, ..., n-1 *)
        (* and that sets FIRST0[0..n - 1] are already computed. *)

        PROCEDURE ComputeFIRST;
            CONST clean = - 1; done = n;

            VAR Stack, Low: ARRAY [0 .. n - 1] OF INTEGER;
                Top: INTEGER;

            PROCEDURE Traverse(v: INTEGER);

                VAR k, j, w, Top1: INTEGER;

            BEGIN
			  INC(Top); Stack[Top] := v; Low[v] := Top; Top1 := Top;
			  FOREACH w such that "v contains-the-FIRSTs-of w" DO
			                    IF Low[w] = clean THEN
			                        Traverse(w);
			                        FIRST[v] := FIRST[v] + FIRST[w]; (*union!*)
			                    END;
			                    IF Low[w] < Low[v] THEN Low[v] := Low[w] END
			  END;
			  IF Low[v] = Top1 THEN (* v root of SCC *)
			      WHILE Top >= Top1 DO w := Stack[Top];
			                        FIRST[w] := FIRST[v]; (*distribute!*)
			          Low[w] := done; DEC(Top)
			      END
			  END
            END Traverse;

            VAR v: INTEGER;

    
        BEGIN
            FOR v := 0 TO n - 1 DO FIRST[v] := FIRST0[v] END; (*init!*)
            Top := - 1;
            FOR v := 0 TO n - 1 DO Low[v] := clean END;
            FOR v := 0 TO n - 1 DO
                IF Low[v] = clean THEN Traverse(v) END
            END
            
            
        END ComputeFIRST;

            PROCEDURE Traverse(v: INTEGER);

                VAR k, j, w, Top1: INTEGER;

            BEGIN
              INC(Top); Stack[Top] := v; Low[v] := Top; Top1 := Top;
              FOREACH w such that "v contains-the-FIRSTs-of w" DO
                                IF Low[w] = clean THEN
                                    Traverse(w);
                                    FIRST[v] := FIRST[v] + FIRST[w]; (*union!*)
                                END;
                                IF Low[w] < Low[v] THEN Low[v] := Low[w] END
              END;
              IF Low[v] = Top1 THEN (* v root of SCC *)
                  WHILE Top >= Top1 DO w := Stack[Top];
                                    FIRST[w] := FIRST[v]; (*distribute!*)
                      Low[w] := done; DEC(Top)
                  END
              END
            END Traverse;
            
        define traverse( x: nonterminal ) =>
        
        STACK FIDDLE
        for each nonterminal w such that `x contains the firsts of w` do
            unless done(w) do
                traverse(w)
                x.first.add( w.first )
            end
            
        end
        
        end
        
        for each nonterminal x do
            x.first := x.basicFirst
        end
        
        for each nonterminal x do
            unless done(x) do traverse(x) end
        end


In general, this algorithm does no more unnecessary set
computations. The underlying graph depth-first graph traversal
algorithm visits each node (nonterminal) exactly once and traverses
each edge (contains-the-FIRSTs-of relationship) exactly once, and it
has linear run-time w.r.t. the size of the graph (or, here, the
grammar). You can hardly do any better.

The algorithm is appropriate because its basic algorithmic structure
corresponds to the structure of the FIRST-computation problem. I
hope I have made that clear enough so that you will agree.

Computing FOLLOW is structurally very similar except for the fact,
of course, that the initial sets FOLLOW0 are different from the sets
FIRST0, and that the graph-spanning relation contains-the-FOLLOWs-of
is different from contains-the-FIRSTs-of.
In other words, a completely different graph will be traversed.
Having understood the above, it shouldn't be hard to derive how
FOLLOW is computed adequately.
*/